1. Technical Field
The present disclosure relates generally to directory services and, more particularly, to a method and apparatus for retrieving and sorting entries from a directory.
2. Description of the Related Art
A directory is a structure that allows users to store and organize information on a computer system. Computer system(s) as referred to herein may include(s) individual computers, servers, computing resources, networks, etc. Directories are specialized databases optimized for reading, browsing, and searching for data and may contain descriptive, attribute based information.
The “Lightweight Directory Access Protocol” (LDAP) is a protocol for accessing directory services, such as X.500 based directory services. In LDAP, data objects, often referred to as data entries, are arranged in a hierarchical tree-like structure that may reflect geographic and/or organizational boundaries or may reflect Internet domain names. Each data entry (except the root entry) in the directory may have a parent entry and a local name, often referred to as a “Relative Distinguished Name” (RDN), or the name of the entry itself. The sum of a data entry's RDN, and all of its parents' RDNs comprise a “Distinguished Name” (DN). A DN is used to refer to each data entry unambiguously and identifies each data entry uniquely in the directory. Therefore, an entry may be referenced by its DN, which may be constructed by taking the RDN and concatenating the names of its ancestor entries.
For example, FIG. 1 is a block diagram illustrating an example directory tree using naming. It is practice to abbreviate the types of entries, so that in the example, ‘c’ stands for “country”, ‘st’ stands for “state”, ‘o’ stands for “organization”, ‘ou’ stands for organizational unit, and ‘cn’ stands for “common name”. In this example, there are two root entries, Australia 101 and the United States 102. The United States is the parent entry for the New York 103 entry. The New York 103 entry is the parent entry for the A 104 entry and the A 104 entry is the parent for organization units, Sales 105 and Research and Development (R&D) 106. Sales 105 is the parent for Alice 107 and Bob 108 and R&D is the parent for Charlie 109. For example, the entry Charlie 109 has an RDN of “Charlie” and a DN of the following: cn=Charlie, ou=R&D, o=A, st=New York, c=United States. The entry Bob 108 has an RDN of “Bob” and a DN of the following: cn=Bob, ou=Sales, o=A, st=New York, and c=United States. The entry A 104 has an RDN of “A” and a DN of the following: o=A, st=New York, and c=United States.
Users may use LDAP to search a directory for information in the directory. The LDAP search operation may allow a portion of the directory to be searched for entries that may match some criteria specified by a search filter. Information may be requested from each entry that matches the filter. For example, a user may want to search the entries directly below the state New York 103 and country United States 102 for organizations with the string “A” 104 in their name, and that have an employee “Charlie” 109.
A user may want to search a directory for a list of DNs that match a particular search criterion and read the results back in the order that they may have been added to the directory. However, one way of executing this search may result in decreased performance for both a client and a server. While a list of DNs may be read back in a single operation, retrieving a list of DNs, with accompanying timestamps for temporal sorting may significantly slow down the search. For example, the server has to return entry attributes in addition to entry names and the client has to maintain the association between the entry name and the timestamp while the server is processing the request.
In addition, a user may want to search a directory for a list of DNs and sort the list to recreate the tree structure that the DNs had when they were first stored in the directory. For example, this may be done for display to users, but may also be required for efficient writing to other directories and data stores. The DNs may be searched and sorted by using string sorts; however, because the DNs are returned in an arbitrary order, a degree of string parsing may also be required. For example, a depth first tree sort may be performed where sibling entries may be sorted alphabetically by RDN. However, the string parsing involved in sorting operations may also result in decreased performance for both a client and a server.
Accordingly, it is desirable to have reliable and effective tools for retrieving and sorting entries from a directory in order to ensure optimum performance.